APIO2019 题解

比赛

$T1. 奇怪装置$

考虑到这有周期性，我们思考时刻 $t1$ 和 $t2$ $(t1 < t2)$ 在何时意义相同：设 $L = t2 - t1$ （$L$ 即是周期大小）

那么那个下取整就可以拆了，整理一下：

有一个定理：$ac \equiv bc(mod m)$，则 $a \equiv b(mod \frac{m}{gcd(m, c)})$，于是

而因为 $gcd(x, x + 1) = 1$ 恒成立，所以

得到了周期大小，我们将区间在模 $L$ 意义下求区间覆盖就好了。

$T2. 桥梁$

1、2、4档部分分都挺好拿的？那不就有 43 pts 了

考虑没有修改操作：对于每个询问，将值大于等于 wi 的边加入并查集，最终答案就是 si 所在并查集大小。但加入修改的话，枚举所有边或者所有操作都 TLE。显然这是因为，询问太多的时候枚举边会炸，修改太多的时候枚举操作会炸。

考虑均摊，把操作分块，设块大小为 S，每过 S 个操作就暴力重构一次。

具体来说，分块处理，将一个块内的所有询问按照重量从大到小排序，边枚举询问边将块内不修改的边插入；而对于块内修改的边，顶多 S 条，用可撤销并查集维护，暴力插入再暴力删除。

O(Q/S * mlogm + QS)，S 取 sqrt(mlogm) 的时候最优。我觉得这个分块很难想到，很神仙（虽然最终复杂度其实是 1e8，需要卡常

代码也太难写了吧！！！啊！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int N = 5e4 + 10, M = 1e5 + 10;
ll n, m, Q, unit;
ll fa[N], sz[N], pos[M], mark[M], pre[M], nxt[M];
ll fax[M], fay[M], szx[M], szy[M], ans[M];
struct edge { int x, y, z, id; }e[M], e2[M];
struct node { int x, y, id; }q1[M], q2[M];

bool cmpe(edge a, edge b) { return a.z > b.z; }
bool cmpq2(node a, node b) { return a.y > b.y; }

inline int getfa(int x) {
    return fa[x] == x ? x : getfa(fa[x]);
}

inline void merge(int x, int y) {
    x = getfa(x), y = getfa(y);
    if (x == y) return;
    if (sz[x] > sz[y]) swap(x, y);
    fa[x] = y, sz[y] += sz[x];
}

inline void read(int &x) {
    int ff = 1, ch;
    while (!isdigit(ch = getchar())) ch == '-' ? ff = -1 : 1;
    x = ch & 15;
    while (isdigit(ch = getchar())) x = (x << 1) + (x << 3) + (ch & 15);
    x = x * ff;
}

inline void solve() {
    unit = max(unit, 1ll);  // !!!!
    for (int o = 1; o <= (Q - 1) / unit + 1; ++o) {
        int l = (o - 1) * unit + 1, r = min(o * unit, Q), l1 = 0, l2 = 0;
        rep(i, 1, m) mark[i] = pre[i] = 0;
        rep(i, 1, r - l + 1) {
            int op; scanf("%d", &op);
            if (op == 1) {
                ++l1;
                read(q1[l1].x), read(q1[l1].y);
                if (pre[q1[l1].x]) nxt[pre[q1[l1].x]] = l1;
                pre[q1[l1].x] = l1;
                nxt[l1] = 0;
                if (!mark[q1[l1].x])  // !!!!
                    mark[q1[l1].x] = i;
                q1[l1].id = i;
            } else {
                ++l2;
                read(q2[l2].x), read(q2[l2].y);
                q2[l2].id = i;
            }
            ans[i] = 0;
        }
        memcpy(e2, e, sizeof(*e) * (m + 1));  // ！！！！！！注意这么写会快很多
        sort(e + 1, e + m + 1, cmpe);
        sort(q2 + 1, q2 + l2 + 1, cmpq2);

        rep(i, 1, n) fa[i] = i, sz[i] = 1;
        int pos = 1;
        rep(i, 1, l2) {
            while (pos <= m && e[pos].z >= q2[i].y) {
                if (!mark[e[pos].id]) {
                    merge(e[pos].x, e[pos].y);
                }
                ++pos;
            }
            rep(j, 1, l1) {
                if (((!nxt[j] || q1[nxt[j]].id > q2[i].id) && q1[j].y >= q2[i].y && q1[j].id < q2[i].id) ||  // 询问前最后一次修改或修改在询问后但之前的边重量符合条件
                    (mark[q1[j].x] > q2[i].id && e2[q1[j].x].z >= q2[i].y)) { // e 排序了，要有个 e2 来存原来的顺序
                    int x = getfa(e2[q1[j].x].x), y = getfa(e2[q1[j].x].y);
                    fax[j] = x, fay[j] = y, szx[j] = sz[x], szy[j] = sz[y];
                    merge(x, y);
                }
            }
            ans[q2[i].id] = sz[getfa(q2[i].x)];
            for (int j = l1; j; --j) {
                if (fax[j]) {
                    int x = fax[j], y = fay[j];
                    fa[x] = x, fa[y] = y, sz[x] = szx[j], sz[y] = szy[j];
                    fax[j] = fay[j] = szx[j] = szy[j] = 0;
                }
            }
        }
        memcpy(e, e2, sizeof(*e) * (m + 1));
        rep(i, 1, l1)
            e[q1[i].x].z = q1[i].y;
        rep(i, 1, r - l + 1)
            if (ans[i]) printf("%lld\n", ans[i]);
    }
}

int main() {
    cin >> n >> m;
    unit = sqrt(m * log(m) / log(2));
    rep(i, 1, m) {
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
        e[i].id = i;
    }
    cin >> Q;
    solve();
    return 0;
}

$T3. 路灯$

两道数据结构题！！！。。。1、2、4 档分好好拿呀= = 看题解学了正解。

考虑在连通区间 $[l, r]$ 中去掉一条边 $[k, k + 1]$，影响的只是 $[l, k]$ 到 $[k + 1, r]$ 的联通性。

考虑将贡献差分，时间段 = 时间点相减：

  • 加入边，$[l, k]$ 到 $[k + 1, r]$ 所有答案 $- i$
  • 删除边，$[l, k]$ 到 $[k + 1, r]$ 所有答案 $+ i$

同时对于询问的时刻 t，若两个点连通，答案要 $+ t$

看到点对，想到转化成平面问题。把区间抽象成坐标，就是二维数点问题，离线用树状数组套线段树或者 CDQ 分治。$O(nlog^2n)$

然而代码先咕咕